package com.duoduo.双指针;

import com.duoduo.ListNode;

/**
 * @program: algorithm
 * @description: 相交链表160
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 *
 * 图示两个链表在节点 c1 开始相交：
 *输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
 * 输出：Intersected at '8'
 * 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
 * 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
 * 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
 * @author: chaidl  ！
 * @create: 2022-04-07 20:05
 */
public class 相交链表160 {
    //双指针
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //先判断两个链表是否为空
        if (headA == null || headB == null) {
            return null;
        }
        ListNode point1 = headA;
        ListNode point2 = headB;
        //在这里只有两种情况，point1==point2，要么都是一个值，要么全部是null
        while (point1 !=point2) {
            point1 = point1 == null ? headB : point1.next;
            point2 = point2 == null ? headA : point2.next;
        }
        return point1;
    }
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        //先计算出两个链表的长度
        int l1=0,l2 = 0,diff=0;
        ListNode point1 = headA;
        ListNode point2 = headB;
        while (point1!=null){
            l1++;
            point1=point1.next;
        }
        while (point2 != null){
            l2++;
            point2 = point2.next;
        }
        //在这里只需要保证point2是长的哪一个就行
        if (l1<l2){
            point1=headA;
            point2=headB;
            diff=l2-l1;
        }else {
            point1=headB;
            point2=headA;
            diff=l1-l2;
        }
        for (int i = 0; i < diff; i++) {
            point2=point2.next;
        }
        while (point1 != null && point2 != null){
            if (point1== point2){
                return point1;
            }
            point1=point1.next;
            point2 = point2.next;
        }
        return null;
    }
}
